#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	checkCapacity(php);
	php->arr[php->size] = x;
	shiftUp(php, php->size);
	php->size++;
}

void shiftUp(HP* php, int child)
{
	int parent = (child - 1) / 2;
	while (parent >= 0) {
		if (php->arr[child] < php->arr[parent])
		{
			swap(php, child, parent);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void swap(HP* php, int i, int j)
{
	HPDataType tmp = php->arr[i];
	php->arr[i] = php->arr[j];
	php->arr[j] = tmp;
}

void checkCapacity(HP* php)
{
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(-1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
}

void HPPop(HP* php)
{
	assert(php && php->size);
	swap(php, 0, php->size - 1);
	php->size--;
	shiftDown(php, 0);
}

void shiftDown(HP* php, int parent)
{
	int childMin = 2 * parent + 1;
	while (childMin < php->size)
	{
		if (childMin + 1 < php->size && php->arr[childMin] > php->arr[childMin + 1])
		{
			childMin = childMin + 1;
		}
		if (php->arr[parent] > php->arr[childMin])
		{
			swap(php, parent, childMin);
			parent = childMin;
			childMin = 2 * childMin + 1;
		}
		else
		{
			break;
		}
	}
}

HPDataType HPTop(HP* php)
{
	assert(php && php->arr);
	return php->arr[0];
}

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}